package com.sort;

import java.util.Arrays;

/**
 * @author yijy
 * @description 数组排序-利用最大堆排序
 * 最大堆：满足完全二叉树，每个节点都大于他的左子节点和右子节点
 * 第一步：构建最大堆
 *
 * 第二步：每次将最大堆的根节点和最末叶子节点进行交换位置
 * 第三步：循环进行第一二步操作
 * @create 2021/3/20 下午7:05
 **/
public class MaxHeapSort {

    public static void main(String []args){
        int []arr = {7,6,7,11,5,12,3,0,1,8,9,20,18,16,13};
        for(int i=arr.length/2-1; i>=0; i--){
            adjustHeap(arr, i, arr.length);
        }

        for(int j=arr.length-1; j>0; j--){
            swap(arr, 0, j);
            adjustHeap(arr, 0, j);
        }
        System.out.println("排序后： "+Arrays.toString(arr));
    }
    //构造最大堆
    public static void adjustHeap(int[] arr, int i, int length){
        //无序数组构造最大堆，从最右边叶子节点的父节点p = length/2-1开始，比较该节点和他的左右子节点，如果p>2p+1 && p>2p，然后从右往左右
        int temp = arr[i];
        for(int k=2*i+1; k<length; k=2*k+1){
            //左子节点和右子节点比较，最大的和父节点比较
            if(k+1<length && arr[k] < arr[k+1]){
                k++;
            }
            if(arr[k] > temp){
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        //将temp放到最终位置
        arr[i] = temp;
    }
    //排序
    public static void swap(int[] arr, int start, int length) {
        int temp = arr[start];
        arr[start] = arr[length];
        arr[length] = temp;
    }


}
